package src.CodeTop;

/**
 * 最大子序和
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * 示例 2：
 *
 * 输入：nums = [1]
 * 输出：1
 * 示例 3：
 *
 * 输入：nums = [0]
 * 输出：0
 * 示例 4：
 *
 * 输入：nums = [-1]
 * 输出：-1
 * 示例 5：
 *
 * 输入：nums = [-100000]
 * 输出：-100000
 */

public class _53MaximumSubarray {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int target = maxSubArray(nums);
        System.out.println(target);
    }

    public static int maxSubArray(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        // 定义与原数组长度相同的数组用来存放每一位的最大子序和
        int[] targets = new int[nums.length];
        // 给新数组首位置赋值
        targets[0] = nums[0];
        // 遍历原数组
        for (int i = 1 ; i < nums.length ; i++) {
            // 当前位置包括之前的累加和
            int sum = nums[i] + targets[i - 1];
            // 若累加和大于当前数值，则赋给新数组这个位置
            if (sum >= nums[i]) {
                targets[i] = sum;
            }else {
                // 若小于当前数值，则将原数组当前数值赋给新数组这个位置
                targets[i] = nums[i];
            }
        }
        // 此时遍历一遍新数组，取出最大的值即可
        int target = targets[0];
        // 打擂台方式获得最大值
        for (int i = 1 ; i < targets.length ; i++) {
            if (targets[i] > target)
                target = targets[i];
        }
        return target;
    }
}
